BZOJ1006【HNOI2008】神奇的国度 <弦图+MCS>

Problem

【HNOI2008】神奇的国度

Description

国是一个热衷三角形的国度，连人的交往也只喜欢三角原则。他们认为三角关系：即相互认识，相互认识，相互认识，是简洁高效的。
为了巩固三角关系，国禁止四边关系，五边关系等等的存在。所谓边关系，是指个人之间仅存在对认识关系：，而没有其它认识关系。比如四边关系指四个人，，，相互认识，而，不认识。
全民比赛时，为了防止做弊，规定任意一对相互认识的人不得在一队。国王想知道，最少可以分多少支队。

Input

第一行两个整数。表示有个人，对认识关系。
接下来行每行输入一对朋友。

Output

输出一个整数，最少可以分多少队。

Sample Input

Sample Output

HINT

标签：弦图 MCS

Solution

弦图与算法参见讲义。

结论：按照任意完美消除序列倒叙染色，每次贪心染能染的最小颜色，可以使颜色数最少。

套上然后模拟染色即可，复杂度。

Code

#include <bits/stdc++.h>
#define MAX_N 10000
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, d[MAX_N+5], c[MAX_N+5], seq[MAX_N+5];
vector <int> G[MAX_N+5]; list <int> buk[MAX_N+5]; bool mrk[MAX_N+5];
void addedge(int u, int v) {G[u].push_back(v), G[v].push_back(u);}
void MCS() {
    memset(mrk, false, sizeof mrk);
    for (int i = 1; i <= n; i++) buk[0].push_back(i);
    for (int i = 0, mx = 0, u; i < n; seq[++i] = u, mrk[u] = true) {
        while (!buk[mx+1].empty()) mx++;
        for (u = -1; u == -1; mx--) {
            while (!buk[mx].empty() && mrk[buk[mx].front()])
                buk[mx].pop_front();
            if (!buk[mx].empty()) u = buk[mx].front();
        }
        for (int j = 0, v; j < (int)G[u].size(); j++) if (!mrk[G[u][j]])
            d[v = G[u][j]]++, buk[d[v]].push_back(v);
    }
}
int Color() {
    int ret = 0;
    memset(mrk, false, sizeof mrk);
    for (int i = 1, u = seq[1]; i <= n; u = seq[++i]) {
        for (int j = 0; j < (int)G[u].size(); j++)
            mrk[c[G[u][j]]] = true;
        for (int j = 1; !c[u]; j++) if (!mrk[j]) c[u] = j;
        for (int j = 0; j < (int)G[u].size(); j++)
            mrk[c[G[u][j]]] = false;
        ret = max(ret, c[u]);
    }
    return ret;
}
int main() {
    read(n), read(m);
    for (int i = 1, u, v; i <= m; i++)
        read(u), read(v), addedge(u, v);
    return MCS(), printf("%d\n", Color()), 0;
}